We analyze Linear Programming (LP) decoding of graphical binary codesoperating over soft-output, symmetric and log-concave channels. We show thatthe error-surface, separating domain of the correct decoding from domain of theerroneous decoding, is a polytope. We formulate the problem of finding thelowest-weight pseudo-codeword as a non-convex optimization (maximization of aconvex function) over a polytope, with the cost function defined by the channeland the polytope defined by the structure of the code. This formulationsuggests new provably convergent heuristics for finding the lowest weightpseudo-codewords improving in quality upon previously discussed. The algorithmperformance is tested on the example of the Tanner [155, 64, 20] code over theAdditive White Gaussian Noise (AWGN) channel.
展开▼
